class Pair {
    constructor(fir, sec) {
        this.fir = fir;
        this.sec = sec;
    }
}

var stoneGame = function (piles) {
    let n = piles.length;

    // 初始化一个n*n的矩阵 dp数组
    let dp = []
    for (let i = 0; i < n; i++) {
        dp[i] = []
    }

    // 在三角区域填充
    for (let i = 0; i < n; i++) {
        for (let j = i; j < n; j++) {
            dp[i][j] = [0, 0]
        }
    }


    // 填入base case
    for (let i = 0; i < n; i++) {
        dp[i][i][0] = piles[i];
        dp[i][i][1] = 0;
    }

    // 斜着遍历数组
    for (let l = 2; l <= n; l++) {
        for (let i = 0; i <= n - 1; i++) {
            let j = l + i - 1;

            // 先手选择最左边或最右边的分数
            let left = piles[i] + dp[i + 1][j][1];
            let right = piles[j] + dp[i][j - 1][1];

            // 套用状态转移方程
            if (left > right) {
                dp[i][j][0] = left;
                dp[i][j][1] = dp[i + 1][j][0];
            } else {
                dp[i][j][0] = right;
                dp[i][j][1] = dp[i][j - 1][0];
            }
        }
    }

    let res = dp[0][n - 1];
    return res[0] - res[1]
};


console.log(stoneGame([3, 9, 1, 2]))